package com.huwaiwai.sort;

public class MyQuickSort {

    public static void quickSort(int[] a) {
        quickSortInternally(a, 0, a.length - 1);
    }

    static void quickSortInternally(int[] a, int s, int e) {
        if (s >= e) {
            return;
        }
        int p = partition(a, s, e);
        // 下表p所在 数据是已经排序好的数据
        quickSortInternally(a, s, p - 1);
        quickSortInternally(a, p + 1, e);
    }

    static int partition(int[] a, int s, int e) {
        // 以数组的最后一个数 作为支点
        int pivot = a[e];
        int index = s;
        for (int i = s; i < e; i++) {
            int temp = a[i];
            if (temp < pivot) {
                if (i == index) {
                    index++;
                } else {
                    a[i] = a[index];
                    a[index++] = temp;
                }
            }
        }
        if (e > index) {
            a[e] = a[index];
            a[index] = pivot;
        }
        return index;
    }

}
